package SkipList;

public class SkipList {
    SkipListNode header; // 跳表的头节点
    SkipListNode tail; // 跳表的尾节点
    private int level; // 跳表的最大层数
    private int size; // 跳表中的元素数量
    private final int MAX_LEVEL = 32; // 跳表的最大层数

    public SkipList() {
        this.header = new SkipListNode(Long.MIN_VALUE, null, MAX_LEVEL); // 头节点中score是最小的
        this.tail = null;
        this.level = 1;
        this.size = 0;
    }

    // 插入
    public void insert(Object value, Double score) {
        // 创建一个最大层数的跳表（无论多少层的元素都可以在update中找到放置的位置）
        SkipListNode[] update = new SkipListNode[MAX_LEVEL];

        // 设置工作指针，初始化指向header
        SkipListNode workNode = header;

        // 查找插入的位置（从上至下）
        for (int i = level - 1; i >= 0; i--) {
            while (workNode.forward[i] != null && workNode.forward[i].getScore() < score) {
                // 向前移动，寻找插入位置
                workNode = workNode.forward[i];
            }

            update[i] = workNode; // 记录当前层的前驱节点，其中"i"保存着第几层
        }

        // 如果节点已存在，更新值
        workNode = workNode.forward[0];
        if (workNode != null && workNode.getScore() == score) {
            workNode.setValue(value);
            return;
        }

        // 插入新的节点
        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level; i < newLevel; i++) {
                update[i] = header; // 增加新层
            }
            level = newLevel; // 更新最大层数
        }

        SkipListNode newNode = new SkipListNode(score, value, newLevel);

        // 从下向上将数据插入到每一层
        for (int i = 0; i < newLevel; i++) {
            // 将该节点插入到相应位置
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;

            // 更新前驱节点的backward指针
            if (newNode.forward[i] != null) newNode.forward[i].backward = newNode;
        }

        newNode.backward = update[0]; // 设置backward指针

        if (newNode.backward != null) newNode.backward.forward[0] = newNode;

        // 如果新节点是最后一个节点，更新尾节点
        if (newNode.forward[0] == null) tail = newNode;

        size++; // 更新节点数量
    }

    // 查找（根据分数找值）
    public SkipListNode find(long score) {
        SkipListNode workNode = header;
        for (int i = level - 1; i >= 0; i--) {
            while (workNode.forward[i] != null && workNode.forward[i].getScore() < score) {
                workNode = workNode.forward[i];
            }
        }
        workNode = workNode.forward[0];
        return workNode != null && workNode.getScore() == score ? workNode : null;
    }

    private int randomLevel() {
        int level = 1;
        while (Math.random() < 0.5 && level < MAX_LEVEL) level++;
        return level;
    }

    // 获取SkipList中全部元素
    public SkipListNode[] getAllData() {
        SkipListNode[] allData = new SkipListNode[size];
        SkipListNode workNode = header.forward[0];
        int skipListIndex = 0;
        while (workNode != null) {
            allData[skipListIndex++] = workNode;
            workNode = workNode.forward[0];
        }
        return allData;
    }

    // 逆向获取SkipList中全部元素
    public SkipListNode[] getAllDataReverse() {
        SkipListNode[] allData = new SkipListNode[size];
        SkipListNode workNode = tail;
        int skipListIndex = 0;
        while (workNode != header) {
            allData[skipListIndex++] = workNode;
            workNode = workNode.backward;
        }
        return allData;
    }
}
